/**
 * @author zjkermit
 * @email zjkermit@gmail.com
 * @date May 21, 2014
 */
package zhoujian.oj.leetcode;

import java.util.ArrayDeque;
import java.util.HashSet;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

import org.junit.Test;

/**
 * @version 1.0
 * @description Given two words (start and end), and a dictionary, find the
 *              length of shortest transformation sequence from start to end,
 *              such that:
 * 
 *              Only one letter can be changed at a time Each intermediate word
 *              must exist in the dictionary
 * 
 *              For example,
 * 
 *              Given:
 * 
 *              start = "hit"
 * 
 *              end = "cog"
 * 
 *              dict = ["hot","dot","dog","lot","log"]
 * 
 *              As one shortest transformation is "hit" -> "hot" -> "dot" ->
 *              "dog" -> "cog", return its length 5.
 * 
 * 
 *              Note:
 * 
 *              Return 0 if there is no such transformation sequence.
 * 
 *              All words have the same length.
 * 
 *              All words contain only lowercase alphabetic characters.
 */
public class WordLadder {

	@Test
	public void test1() {
		HashSet<String> dict = new HashSet<String>();
		dict.add("hot");
		dict.add("cog");
		dict.add("dog");
		dict.add("tot");
		dict.add("hog");
		dict.add("hop");
		dict.add("pot");
		dict.add("dot");

		assert ladderLength("hot", "dog", dict) == 3;
	}

	@Test
	public void test2() {
		HashSet<String> dict = new HashSet<String>();
		String[] arr = { "si", "go", "se", "cm", "so", "ph", "mt", "db", "mb",
				"sb", "kr", "ln", "tm", "le", "av", "sm", "ar", "ci", "ca",
				"br", "ti", "ba", "to", "ra", "fa", "yo", "ow", "sn", "ya",
				"cr", "po", "fe", "ho", "ma", "re", "or", "rn", "au", "ur",
				"rh", "sr", "tc", "lt", "lo", "as", "fr", "nb", "yb", "if",
				"pb", "ge", "th", "pm", "rb", "sh", "co", "ga", "li", "ha",
				"hz", "no", "bi", "di", "hi", "qa", "pi", "os", "uh", "wm",
				"an", "me", "mo", "na", "la", "st", "er", "sc", "ne", "mn",
				"mi", "am", "ex", "pt", "io", "be", "fm", "ta", "tb", "ni",
				"mr", "pa", "he", "lr", "sq", "ye" };
		for (String s : arr)
			dict.add(s);

		assert ladderLength("qa", "sq", dict) == 5;
	}

	@Test
	public void test3() {
		HashSet<String> dict = new HashSet<String>();
		String[] arr = { "dose", "ends", "dine", "jars", "prow", "soap",
				"guns", "hops", "cray", "hove", "ella", "hour", "lens", "jive",
				"wiry", "earl", "mara", "part", "flue", "putt", "rory", "bull",
				"york", "ruts", "lily", "vamp", "bask", "peer", "boat", "dens",
				"lyre", "jets", "wide", "rile", "boos", "down", "path", "onyx",
				"mows", "toke", "soto", "dork", "nape", "mans", "loin", "jots",
				"male", "sits", "minn", "sale", "pets", "hugo", "woke", "suds",
				"rugs", "vole", "warp", "mite", "pews", "lips", "pals", "nigh",
				"sulk", "vice", "clod", "iowa", "gibe", "shad", "carl", "huns",
				"coot", "sera", "mils", "rose", "orly", "ford", "void", "time",
				"eloy", "risk", "veep", "reps", "dolt", "hens", "tray", "melt",
				"rung", "rich", "saga", "lust", "yews", "rode", "many", "cods",
				"rape", "last", "tile", "nosy", "take", "nope", "toni", "bank",
				"jock", "jody", "diss", "nips", "bake", "lima", "wore", "kins",
				"cult", "hart", "wuss", "tale", "sing", "lake", "bogy", "wigs",
				"kari", "magi", "bass", "pent", "tost", "fops", "bags", "duns",
				"will", "tart", "drug", "gale", "mold", "disk", "spay", "hows",
				"naps", "puss", "gina", "kara", "zorn", "boll", "cams", "boas",
				"rave", "sets", "lego", "hays", "judy", "chap", "live", "bahs",
				"ohio", "nibs", "cuts", "pups", "data", "kate", "rump", "hews",
				"mary", "stow", "fang", "bolt", "rues", "mesh", "mice", "rise",
				"rant", "dune", "jell", "laws", "jove", "bode", "sung", "nils",
				"vila", "mode", "hued", "cell", "fies", "swat", "wags", "nate",
				"wist", "honk", "goth", "told", "oise", "wail", "tels", "sore",
				"hunk", "mate", "luke", "tore", "bond", "bast", "vows", "ripe",
				"fond", "benz", "firs", "zeds", "wary", "baas", "wins", "pair",
				"tags", "cost", "woes", "buns", "lend", "bops", "code", "eddy",
				"siva", "oops", "toed", "bale", "hutu", "jolt", "rife", "darn",
				"tape", "bold", "cope", "cake", "wisp", "vats", "wave", "hems",
				"bill", "cord", "pert", "type", "kroc", "ucla", "albs", "yoko",
				"silt", "pock", "drub", "puny", "fads", "mull", "pray", "mole",
				"talc", "east", "slay", "jamb", "mill", "dung", "jack", "lynx",
				"nome", "leos", "lade", "sana", "tike", "cali", "toge", "pled",
				"mile", "mass", "leon", "sloe", "lube", "kans", "cory", "burs",
				"race", "toss", "mild", "tops", "maze", "city", "sadr", "bays",
				"poet", "volt", "laze", "gold", "zuni", "shea", "gags", "fist",
				"ping", "pope", "cora", "yaks", "cosy", "foci", "plan", "colo",
				"hume", "yowl", "craw", "pied", "toga", "lobs", "love", "lode",
				"duds", "bled", "juts", "gabs", "fink", "rock", "pant", "wipe",
				"pele", "suez", "nina", "ring", "okra", "warm", "lyle", "gape",
				"bead", "lead", "jane", "oink", "ware", "zibo", "inns", "mope",
				"hang", "made", "fobs", "gamy", "fort", "peak", "gill", "dino",
				"dina", "tier" };
		for (String s : arr)
			dict.add(s);

		long s = System.currentTimeMillis();
		System.out.println(ladderLength("nape", "mild", dict));
		System.out.println(System.currentTimeMillis() - s);
	}

	// bfs
	public int ladderLength(String start, String end, HashSet<String> dict) {
		ArrayDeque<String> queue = new ArrayDeque<String>();
		ArrayDeque<Integer> dis = new ArrayDeque<Integer>();
		dis.add(1);
		Iterator<String> it;
		queue.push(start);
		while (!queue.isEmpty()) {
			int distance = dis.pop();
			String s = queue.pop();

			if (helper(s, end))
				return distance + 1;

			it = dict.iterator();
			while (it.hasNext()) {
				String ss = it.next();
				if (helper(s, ss)) {
					queue.add(ss);
					dis.add(distance + 1);
					it.remove();
				}
			}
		}

		return 0;
	}

	private boolean helper(String s1, String s2) {
		int count = 0;
		for (int i = 0; i < s1.length(); ++i) {
			if (count > 1)
				return false;
			if (s1.charAt(i) != s2.charAt(i))
				++count;
		}
		return count == 1;
	}

	// another solution, better
	public int solution2(String start, String end, HashSet<String> dict) {
		Set<String> set = new HashSet<String>();
		Queue<String> queue = new LinkedList<String>();
		queue.offer(start);
		int distance = 1;
		int count = 1;
		set.add(start);

		while (count > 0) {
			while (count > 0) {
				char[] curr = queue.poll().toCharArray();
				for (int i = 0; i < curr.length; i++) {
					char tmp = curr[i];
					for (char c = 'a'; c <= 'z'; c++) {
						if (c == tmp)
							continue;
						curr[i] = c;
						String str = new String(curr);
						if (str.equals(end))
							return distance + 1;
						if (dict.contains(str) && !set.contains(str)) {
							queue.offer(str);
							set.add(str);
						}
					}
					curr[i] = tmp;
				}
				count--;
			}
			distance++;
			count = queue.size();
		}
		
		return 0;
	}

	@Test
	public void test4() {
		HashSet<String> dict = new HashSet<String>();
		String[] arr = { "dose", "ends", "dine", "jars", "prow", "soap",
				"guns", "hops", "cray", "hove", "ella", "hour", "lens", "jive",
				"wiry", "earl", "mara", "part", "flue", "putt", "rory", "bull",
				"york", "ruts", "lily", "vamp", "bask", "peer", "boat", "dens",
				"lyre", "jets", "wide", "rile", "boos", "down", "path", "onyx",
				"mows", "toke", "soto", "dork", "nape", "mans", "loin", "jots",
				"male", "sits", "minn", "sale", "pets", "hugo", "woke", "suds",
				"rugs", "vole", "warp", "mite", "pews", "lips", "pals", "nigh",
				"sulk", "vice", "clod", "iowa", "gibe", "shad", "carl", "huns",
				"coot", "sera", "mils", "rose", "orly", "ford", "void", "time",
				"eloy", "risk", "veep", "reps", "dolt", "hens", "tray", "melt",
				"rung", "rich", "saga", "lust", "yews", "rode", "many", "cods",
				"rape", "last", "tile", "nosy", "take", "nope", "toni", "bank",
				"jock", "jody", "diss", "nips", "bake", "lima", "wore", "kins",
				"cult", "hart", "wuss", "tale", "sing", "lake", "bogy", "wigs",
				"kari", "magi", "bass", "pent", "tost", "fops", "bags", "duns",
				"will", "tart", "drug", "gale", "mold", "disk", "spay", "hows",
				"naps", "puss", "gina", "kara", "zorn", "boll", "cams", "boas",
				"rave", "sets", "lego", "hays", "judy", "chap", "live", "bahs",
				"ohio", "nibs", "cuts", "pups", "data", "kate", "rump", "hews",
				"mary", "stow", "fang", "bolt", "rues", "mesh", "mice", "rise",
				"rant", "dune", "jell", "laws", "jove", "bode", "sung", "nils",
				"vila", "mode", "hued", "cell", "fies", "swat", "wags", "nate",
				"wist", "honk", "goth", "told", "oise", "wail", "tels", "sore",
				"hunk", "mate", "luke", "tore", "bond", "bast", "vows", "ripe",
				"fond", "benz", "firs", "zeds", "wary", "baas", "wins", "pair",
				"tags", "cost", "woes", "buns", "lend", "bops", "code", "eddy",
				"siva", "oops", "toed", "bale", "hutu", "jolt", "rife", "darn",
				"tape", "bold", "cope", "cake", "wisp", "vats", "wave", "hems",
				"bill", "cord", "pert", "type", "kroc", "ucla", "albs", "yoko",
				"silt", "pock", "drub", "puny", "fads", "mull", "pray", "mole",
				"talc", "east", "slay", "jamb", "mill", "dung", "jack", "lynx",
				"nome", "leos", "lade", "sana", "tike", "cali", "toge", "pled",
				"mile", "mass", "leon", "sloe", "lube", "kans", "cory", "burs",
				"race", "toss", "mild", "tops", "maze", "city", "sadr", "bays",
				"poet", "volt", "laze", "gold", "zuni", "shea", "gags", "fist",
				"ping", "pope", "cora", "yaks", "cosy", "foci", "plan", "colo",
				"hume", "yowl", "craw", "pied", "toga", "lobs", "love", "lode",
				"duds", "bled", "juts", "gabs", "fink", "rock", "pant", "wipe",
				"pele", "suez", "nina", "ring", "okra", "warm", "lyle", "gape",
				"bead", "lead", "jane", "oink", "ware", "zibo", "inns", "mope",
				"hang", "made", "fobs", "gamy", "fort", "peak", "gill", "dino",
				"dina", "tier" };
		for (String s : arr)
			dict.add(s);

		long s = System.currentTimeMillis();
		System.out.println(solution2("nape", "mild", dict));
		System.out.println(System.currentTimeMillis() - s);
	}
}
